The use of caches in conjunction with processors has been shown to be very effective in speeding up the rate that instructions are executed. The cache is a memory which is relatively small compared to main memory but which is very fast. The cache is used to provide very fast access to the instructions and/or data which are frequently used. There may or may not be separate caches for instructions (or code) and data. Whether the information is actually instructions or data, the information can be referred to as simply data. There has developed circuitry for keeping track of data which is contained in the cache. The common approach has been to use what is commonly known as TAGs as part of the cache to aid in identifying a request for data or an instruction which is contained in the cache. The processor submits a request for data or an instruction in the form of an address. The TAG is used to determine if the address generated by the processor is one for which the cache has the needed data. The TAG has TAG locations for storing TAG addresses for which information is contained in the cache. The address generated by the processor is compared to the TAG addresses. If the processor-generated address is also a TAG address then the cache does have the requested data. When this occurs it is generally considered a "hit," and a hit signal is generated. There have been discovered solutions to some of the problems inherent in a TAG. One of the problems is at "start-up" when none of the information in the cache and none of the addresses in the TAG have been set. A solution to this problem has been the use of a valid bit which is set when information is stored in the cache which corresponds to a TAG address. If the valid bit is not set, then the hit signal is suppressed for that generated address. The setting of the valid bit is set by the cache when information is written into the cache. As the processor processes data and instructions, the most used address locations may change. Thus, the cache may be full of valid information, but that information may not be the information which is being frequently used. A technique for keeping track of the least recently used TAG locations has been developed to keep the information in the cache not only valid but also current. Least-recently-used (LRU) logic has been developed for keeping track of the least recently used TAG locations. When there is a miss in the cache, there is then an access to main memory. When the main memory returns the information to the processor, the cache also stores this information and the corresponding TAG address in a TAG location. The LRU logic determines which TAG location is the one that should be replaced by the most recent address which missed in the cache. The replaced TAG location is the one which the LRU logic determined was the least recently used TAG address.
A cache may have, in one extreme, completely fixed addresses. If the TAG addresses are fixed, then there is no need to keep track of the least recently used TAG address because the TAG addresses are fixed. The information which corresponds to the TAG address is the only thing which can be updated. The determination of a hit on the TAG address is very simple because the TAG addresses are hard wired. In another extreme, any TAG location can have any address generated by the processor. In such a case, the determination of a TAG address hit requires reading all of the stored TAG addresses and performing a comparison of each of them with the address generated by the processor. This type of cache is known as a fully associative cache. There is a compromise approach in which certain of the TAG locations can have limited variability. There may be, for example, sets of four TAG locations in which each of the four TAG locations within a set has some bits in common and a some that are variable. The common address bits (which comprise what is known as the "index") are thus hard-wired so that in response to an address generated by the processor, one set of four TAG locations is accessed. In such a case, the address generated by the processor can be considered to have an index portion and a TAG portion. The four TAG addresses present in the four TAG locations accessed by the index portion of the processor-generated address are read and compared to the TAG portion of the generated address. If one of the TAG addresses in the accessed TAG locations and the TAG portion of the generated address are the same, then there is a TAG hit. If the data which corresponds to the hit TAG location is valid, then the hit signal is generated and the information which corresponds to the hit TAG location is provided to the processor. Another similar approach to the set-associative approach, is for there to be a single TAG location for the index portion of the generated address. In such a case, only a single TAG address is compared to the TAG portion of the generated address.
There are other problems with caches. They are generally hard to test because the TAG addresses, which are critical to the operation of the cache, are not actually output from the cache. Thus, if the circuitry in the cache which stores the TAG addresses is to be tested, it must be tested indirectly. The TAG addresses themselves are not actually read but must be verified by inference. This is also true of the valid bits and the LRU bits. Even to read data from the cache, there must first be a hit with the address so even data locations are read by inference. Another characteristic of caches is that if a single bit in the cache becomes defective, the whole cache, as is the case in a typical integrated circuit memory, is no longer usable. The whole cache or the whole integrated circuit must either be replaced or mapped out of the system by software.